package main

import (
	"bytes"
	"fmt"
	"go-study/algorithm/standard"
	"strconv"
)

// 如何求数字的组合

func main() {
	numGroup := NewNumGroup([]int{1, 2, 2, 3, 4, 5})
	numGroup.getAllCombinations()
	numGroup.printAllCombinations()
}

type NumGroup struct {
	numbers     []int
	n           int
	visited     []bool
	graph       [][]int
	combination []int
	s           *standard.Set
}

func NewNumGroup(arr []int) *NumGroup {
	return &NumGroup{
		numbers:     arr,
		n:           len(arr),
		visited:     make([]bool, len(arr)),
		graph:       make([][]int, len(arr)),
		combination: make([]int, 0),
		s:           standard.NewSet(),
	}
}

// 转化 int 数组为 string
func iToS(a []int) string {
	var buff bytes.Buffer
	for _, v := range a {
		buff.WriteString(strconv.Itoa(v))
	}
	return buff.String()
}

// 对图从节点 start 位置开始进行深度遍历
func (p *NumGroup) depthFirstSearch(start int) {
	p.visited[start] = true
	p.combination = append(p.combination, p.numbers[start])

	// 遍历完所有节点之后，如果第 3 个节点的值不为 4，则添加到集合中去
	if len(p.combination) == p.n {
		if p.combination[2] != 4 {
			p.s.Add(iToS(p.combination))
		}
	}

	for j := 0; j < p.n; j++ {
		// 当这两个节点是连通的且这个点没有被访问过
		if p.graph[start][j] == 1 && !p.visited[j] {
			p.depthFirstSearch(j)
		}
	}

	p.combination = p.combination[:len(p.combination)-1]
	p.visited[start] = false
}

// 获取 1,2,2,3,4,5 的左右组合，使得 "4" 不能在第三位，3 与 5 不能相连
func (p *NumGroup) getAllCombinations() {
	for i := range p.graph {
		p.graph[i] = make([]int, p.n)
	}

	for i := 0; i < p.n; i++ {
		for j := 0; j < p.n; j++ {
			if i == j {
				p.graph[i][j] = 0
			} else {
				p.graph[i][j] = 1
			}
		}
	}

	p.graph[3][5] = 0
	p.graph[5][3] = 0

	for i := 0; i < p.n; i++ {
		p.depthFirstSearch(i)
	}
}

func (p *NumGroup) printAllCombinations() {
	res := p.s.List()
	for _, v := range res {
		fmt.Println(v)
	}
}
